package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-20 17:09
 * @Description: PalindromePartitioningII$132-分隔回文串-https://leetcode-cn.com/problems/palindrome-partitioning-ii/
 */
public class PalindromePartitioningII {
	/**
	 *
	 * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
	 *
	 * 返回符合要求的最少分割次数。
	 *
	 * 示例:
	 *
	 * 输入: "aab"
	 * 输出: 1
	 * 解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/palindrome-partitioning-ii
	 *
	 * step 1:确定状态
	 *      最后一步：最优策略中，最后一段回文字符串,设为S[j...N-1]
	 *          需要直到前j个字符[0...j-1]最少可以划分成多少个回文串
	 *      子问题：
	 *          求S前N个字符S[0,N-1]最少划分为几个回文字符串
	 *          需要知道S前j个字符[0...j-1]最少可以划分成几个回文串
	 *       状态：设f[i]=字符串S前i个字符最少可以被会分成几个回文串
	 * step 2:状态方程
	 *                 f[i] = min(0,1...i-1){         f[j]+1                   |   S[j...,i-1]是回文串}
	 *            S前i个字符最少可以划分为多少回文串  S前j个字符最少可以划分成多少回文串       最后一段回文串
	 *
	 *  j的范围是0~(i-1),因为至少为最后一个i留一个回文串
	 *
	 *
	 * step 3:初始值和边界值
	 *      设f[i]=字符串S前i个字符最少可以被会分成几个回文串
	 *       f[i] = min(0,1...i-1){f[j]+1 | S[j...,i-1]是回文串}
	 *
	 *          初始条件：空串可以被分成0个回文串
	 *          使用序列型思路
	 *          f[0] = 0
	 *
	 *
	 * step 4:计算顺序
	 *          计算f[0],f[1],...,f[N]
	 *
	 *          判断S[j,...,i-1]是不是回文串，正常通过双指针，时间复杂度O（n）,如此O(n)=n^3,太慢，优化
	 *
	 *      记录回文串
	 *          奇数：以字符串每一个字符为中心，向两边扩展，找到所有回文串
	 *          偶数：以中心轴为中心向两边扩展，找到所有回文串
	 *
	 *      找到回文串后，通过数据isPalin[i][j]表示S[i,...,j]是否是回文串
	 *
	 *  时间复杂度：O(n^2)
	 *   f[i] = min(0,1...i-1){f[j]+1 | S[j...,i-1]是回文串}
	 *      等价于
	 *    f[i] = min(0,1...i-1){f[j]+1 | isPalin[j][i-1]=true}
	 *
	 *  注意答案是f[N]-1(题目要求最少划分几次)
	 *
	 *  时间复杂度O(n^2),空间复杂度O(n^2)
	 *
	 */

	public int minCut(String s) {

		char[] chars = s.toCharArray();
		int n = chars.length;
		if(n == 0){
			return 0;
		}

		boolean[][] isPalin = new boolean[n][n];

		int i,j,t;

		for (i = 0; i < n; i++) {
			for (j = i; j < n ; j++) {
				isPalin[i][j] = false;
			}
		}

		//generate palindrome
		// 枚举中心点
		for(t=0;t<n;t++){{
			// odd length
			//两个不会重复，i+j永远都是偶数，寻找所有奇数可能的字符串
			i = j = t;
			while (i>=0&&j<n&&chars[i]==chars[j]){
				isPalin[i][j] = true;
				i--;
				j++;
			}

			//even length
			// i+j永远都是计数，寻找所有偶数可能的回文串
			i = t;
			j = t+1;
			while (i>=0&&j<n&&chars[i]==chars[j]){
				isPalin[i][j] = true;
				i--;
				j++;
			}
		}}

		int[] f = new int[n+1];
		f[0] = 0;

		for (i = 1;  i<=n ; i++) {
			//  f[i] = min(0,1...i-1){f[j]+1 | isPalin[j][i-1]=true}
			f[i] = Integer.MAX_VALUE;
			//f[i] = i; 也可以，每个字符作为一个回文串，最大就是i
			for (j = 0;  j<i ; j++) {
				if(isPalin[j][i-1]){
					f[i] = Math.min(f[j]+1,f[i]);
				}
			}
		}



		return f[n]-1;
	}

	public static void main(String[] args) {
		String str = "aab";
		PalindromePartitioningII instance = new PalindromePartitioningII();
		System.out.println(instance.minCut(str));

	}
}
